// https://leetcode.cn/problems/find-pivot-index/

// 题干：给你一个整数数组 nums ，请计算数组的 中心下标 。
//      数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
//      如果中心下标位于数组最左端，那么左侧数之和视为 0 ，
//      因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
//      如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

// 示例：输入：nums = [1, 7, 3, 6, 5, 6]
//       输出：3

// 碎语：前缀和的应用题目，不同的是还需要一个后缀和

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int pivotIndex(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> pre(n), post(n);

        // 构建前缀和和后缀和数组
        for (int i = 1 ; i < n ; i++) pre[i] = pre[i - 1] + nums[i - 1];
        for (int i = n - 2 ; i >= 0 ; i--) post[i] = post[i + 1] + nums[i + 1];

        // 从左到右遍历数组，得出最左侧答案
        for (int i = 0 ; i < n ; i++){
            if (pre[i] == post[i]) return i;
        }

        return -1; // 若不存在，则返回-1
    }
};

int main()
{
    Solution sol;
    vector<int> nums = {1,7,3,6,5,6};

    cout << sol.pivotIndex(nums) << endl;

    return 0;
}